/*
 *   带回血的约瑟夫问题
**/
#include <stdio.h>
#include <stdlib.h>

struct Node{
    int hp;                 // 血量
    int index;              // 序号
    int add_flag;           // 0:没加血，1:加过血
    int left;               // 0:左边人没死，1:左边人死了
    int right;              // 0:右边人没死，1:右边人死了

    struct Node *next;
    struct Node *prev;
};

struct Node *doub_list_create(int num){
    if(num <= 0){
        return NULL;
    }
    struct Node *head, *ptmp;
    int i;
    head = (struct Node *)malloc(sizeof(struct Node));
    head->add_flag = 0;
    head->index = 1;
    head->hp = 1;
    head->left = 0;
    head->right = 0;
    ptmp = head;
    for(i=2; i<=num; ++i){
        ptmp->next = (struct Node *)malloc(sizeof(struct Node));
        ptmp->next->prev = ptmp;
        ptmp->next->add_flag = 0;
        ptmp->next->index = i;
        ptmp->next->hp = 1;
        ptmp->next->left = 0;
        ptmp->next->right = 0;
        ptmp = ptmp->next;
    }
    ptmp->next = head;
    head->prev = ptmp;
    return head;
}

int loop_nm(int n, int m){
    struct Node *head = doub_list_create(n);
    struct Node *ptmp;
    int i, j;
    head = head->prev;          //退一步，下一个节点为删除节点
    for(i=1; i<n; ++i){
        for(j=1; j<m; ++j){
            head = head->next;
        }
        ptmp = head->next;      // tmp指向要删除的节点
        if(--ptmp->hp > 0){
            continue;
        }
        else{
            ptmp->next->left = 1;
            ptmp->prev->right = 1;
            if(ptmp->next->add_flag==0){
                if(ptmp->next->left&&ptmp->next->right){
                    ++ptmp->next->hp;
                    ptmp->next->add_flag = 1;
                }
            }
            if(ptmp->prev->add_flag==0){
                if(ptmp->prev->left&&ptmp->prev->right){
                    ++ptmp->prev->hp;
                    ptmp->prev->add_flag = 1;
                }
            }
            head->next = ptmp->next;
            ptmp->next->prev = head;
            free(ptmp);
        }
    }
    return head->index;
}

int main(void)
{
    printf("%d\n", loop_nm(4, 2));
    return 0;
}
